package algorithm.sort;

import algorithm.heap.MaxHeap;
import algorithm.sort.common.SortTestHelper;

/**
 * @author bingo
 * @create 2018-02-25 15:19
 **/
public class HeapSort {

    public void sort(Comparable[] arr){
        int n=arr.length;
        MaxHeap maxHeap = new MaxHeap(n);
        for(int i=0;i<n;i++){
           maxHeap.insert((int)arr[i]);
        }
        for(int i=n-1;i>=0;i--){
            arr[i]=maxHeap.push();
        }
    }

    public static void main(String[] args) {
        Integer[] arr = SortTestHelper.generateRandomArray(100000, 0, 100000);
       HeapSort heapSort = new HeapSort();
       long start = System.currentTimeMillis();
       heapSort.sort(arr);
       long end = System.currentTimeMillis();
       System.out.println(SortTestHelper.isSorted(arr));
        System.out.println("堆排序耗时:"+(end-start)+"ms");
    }
}
